#include<vector>
using namespace std;

int change(int amount, vector<int>& coins) {
    int n = coins.size();
    vector<vector<double>> dp(n + 1, vector<double>(amount + 1));
    dp[0][0] = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= amount; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if (j >= coins[i - 1]) dp[i][j] += dp[i][j - coins[i - 1]];
        }
    }
    return dp[n][amount];
}

int numSquares(int n) {
    vector<int> count;
    for (int i = 1; i <= n; i++)
    {
        if (i * i <= n) count.push_back(i * i);
        else break;
    }
    int m = count.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int j = 1; j <= n; j++) dp[0][j] = 0x3f3f3f3f;
    dp[0][0] = 0;
    for (int i = 1; i <= m; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if (j >= count[i - 1]) dp[i][j] = min(dp[i][j], dp[i][j - count[i - 1]] + 1);
        }
    }
    return dp[m][n];
}

int main()
{
    vector<int> v{ 1,35,643,631,2 };
    change(5, v);
    numSquares(1);

	return 0;
}